/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 求树的高度
int TreeHeight(struct TreeNode* root){
    if(root == NULL)
        return 0;
    return fmax(TreeHeight(root->left),TreeHeight(root->right))+1;
}

bool isBalanced(struct TreeNode* root){
    if(root == NULL)
        return true;
    int dif = TreeHeight(root->left)-TreeHeight(root->right);
    // 依次求每个子树是否平衡
    if(dif <= 1 && dif >= -1 && isBalanced(root->left) &&\
        isBalanced(root->right)){
        return true;
    }
    
    return false;
}